Gene transcription in eukaryotes is associated with conformational changes of a large area of chromatin adjacent to a gene. This rearrangement may involve the whole loop (topological domain) to which a given gene belongs.Regulatory events associated with activation or inactivation of transcription are found to act through relatively short nucleotide sequences, often located several thousand base pairs apart from gene. These sequences, termed enhancers may act independently on their distance from or orientation with respect to the gene.Both long‐range conformational rearrangements (...) of chromatin and any long distance effects of enhancers may be associated with elastic torsional strain in DNA, arising in transcriptionally active chromatin loops. Enhancer effects, in particular, may be associated with conformational transitions in DNA competing for the energy deposited in the elastic spring of the DNA. (shrink)

We characterize the linear order types $\tau $ with the property that given any countable linear order $\mathcal {L}$, $\tau \cdot \mathcal {L}$ is a computable linear order iff $\mathcal {L}$ is a computable linear order, as exactly the finite nonempty order types.

In this paper we prove that any Δ30 degree has an increasing η -representation. Therefore, there is an increasing η -representable set without a strong η -representation.

To analyze some sсeptical arguments was build the epistemological model about only one perceiving subject “Enarch”: he is one (ἐνᾴϛ) and has beginning (ἀρχῄ) in itself. This model was applyed for critical analysis of Husserl’s and Putnam’s attempts to overcome scepticism (i) by using “the intersubjective program” in a first case and (ii) argument “brains in a vat” in a second one. To justify the equivalence of the “intersubjectiveness” and “objectiveness” Husserl suggested the existence of transcendental Community. The main goal (...) of the paper is to show that intersubjective epistemology faces the difficulty: the equivalence of the“intersubjectiveness” and “objectiveness” is not feasible. Developing Putnam’s model “brains in a vat” about boundaries of scepticism has been formulated the argument about “back of the head”. It showed that skepticism is much more strictly doctrine than it was suggested by Putnam. (shrink)

Andrey Tashchian | : Chez saint Augustin le numerus sert de principe ontologique de la beauté finie en révélant l’ascension métaphysique du sensible vers l’intelligible. De plus, se divisant en sphères objective et subjective, le numerus s’avère être une totalité, « l’idée ». Toutefois, comme une forme de la culture antique, ce concept n’est pas connu comme une contradiction réelle, et ainsi les numeri éternels ne sont pas postulés comme un processus où la subjectivité finie, le moi, deviendrait nécessaire (...) pour la substance infinie. Donc, dans la doctrine de saint Augustin, l’essence de la science de la musique n’a pas la valeur de l’activité humaine consciente de soi. | : In St. Augustine’s doctrine of rhythm numerus manifests the metaphysical ascent from sensuousness to rationality and is the ontological root of finite beauty. Moreover, numerus is differentiated into the objective and subjective spheres, proving to be a totality, the “idea.” Meanwhile, as a formation of antique culture, this concept is not known as a real contradiction, and thereby eternal numeri are not posited as a process in which finite subjectivity, I would be a necessity for the infinite substance. So, in St. Augustine’s doctrine the essence of the science of music has not the value of man’s self-conscious activity. (shrink)

This note is part of the implementation of a programme in foundations of mathematics to find exact threshold versions of all mathematical unprovability results known so far, a programme initiated by Weiermann. Here we find the exact versions of unprovability of the finite graph minor theorem with growth rate condition restricted to planar graphs, connected planar graphs and graphs embeddable into a given surface, assuming an unproved conjecture : ‘there is a number a>0 such that for all k≥3, and all (...) n≥1, the proportion of connected graphs among unlabelled planar graphs of size n omitting the k-element circle as minor is greater than a’. Let γ be the unlabelled planar growth constant . Let P be the following first-order arithmetical statement with real parameter c: “for every K there is N such that whenever G1,G2,…,GN are unlabelled planar graphs with Gishrink)

Cohesive powersof computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let$\omega $,$\zeta $, and$\eta $denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of$\omega $. If$\mathcal {L}$is a computable copy of$\omega $that is computably isomorphic to the usual presentation of$\omega $, then every cohesive power of$\mathcal {L}$has order-type$\omega + (...) \zeta \eta $. However, there are computable copies of$\omega $, necessarily not computably isomorphic to the usual presentation, having cohesive powers not elementarily equivalent to$\omega + \zeta \eta $. For example, we show that there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \eta $. Our most general result is that if$X \subseteq \mathbb {N} \setminus \{0\}$is a Boolean combination of$\Sigma _2$sets, thought of as a set of finite order-types, then there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$, where$\boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$denotes the shuffle of the order-types inXand the order-type$\omega + \zeta \eta + \omega ^*$. Furthermore, ifXis finite and non-empty, then there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \boldsymbol {\sigma }(X)$. (shrink)

In the present paper we discuss: a) how Hilbert’s unification program failed completely, and b) we outline a new electron model based on Helmholtz’s electron vortex and Kolmogorov theory of turbulence. Novelty aspect: we discuss among other things, electron capture event, and von Karman vortex street. We also discuss a new model of origination of charge and matter. This paper is a sequel to a preceding paper on similar theme.

Review by: Jan Reimann The Bulletin of Symbolic Logic, Volume 19, Issue 3, Page 397-399, September 2013.

Propensities are presented as a generalization of classical determinism. They describe a physical reality intermediary between Laplacian determinism and pure randomness, such as in quantum mechanics. They are characterized by the fact that their values are determined by the collection of all actual properties. It is argued that they do not satisfy Kolmogorov axioms; other axioms are proposed.

Correlations of spins in a system of entangled particles are inconsistent with Kolmogorov’s probability theory (KPT), provided the system is assumed to be non-contextual. In the Alice–Bob EPR paradigm, non-contextuality means that the identity of Alice’s spin (i.e., the probability space on which it is defined as a random variable) is determined only by the axis $\alpha _{i}$ chosen by Alice, irrespective of Bob’s axis $\beta _{j}$ (and vice versa). Here, we study contextual KPT models, with two properties: (1) (...) Alice’s and Bob’s spins are identified as $A_{ij}$ and $B_{ij}$ , even though their distributions are determined by, respectively, $\alpha _{i}$ alone and $\beta _{j}$ alone, in accordance with the no-signaling requirement; and (2) the joint distributions of the spins $A_{ij},B_{ij}$ across all values of $\alpha _{i},\beta _{j}$ are constrained by fixing distributions of some subsets thereof. Of special interest among these subsets is the set of probabilistic connections, defined as the pairs $\left( A_{ij},A_{ij'}\right) $ and $\left( B_{ij},B_{i'j}\right) $ with $\alpha _{i}\not =\alpha _{i'}$ and $\beta _{j}\not =\beta _{j'}$ (the non-contextuality assumption is obtained as a special case of connections, with zero probabilities of $A_{ij}\not =A_{ij'}$ and $B_{ij}\not =B_{i'j}$ ). Thus, one can achieve a complete KPT characterization of the Bell-type inequalities, or Tsirelson’s inequalities, by specifying the distributions of probabilistic connections compatible with those and only those spin pairs $\left( A_{ij},B_{ij}\right) $ that are subject to these inequalities. We show, however, that quantum-mechanical (QM) constraints are special. No-forcing theorem says that if a set of probabilistic connections is not compatible with correlations violating QM, then it is compatible only with the classical–mechanical correlations. No-matching theorem says that there are no subsets of the spin variables $A_{ij},B_{ij}$ whose distributions can be fixed to be compatible with and only with QM-compliant correlations. (shrink)

In 1933 Godel introduced a calculus of provability (also known as modal logic S4) and left open the question of its exact intended semantics. In this paper we give a solution to this problem. We find the logic LP of propositions and proofs and show that Godel's provability calculus is nothing but the forgetful projection of LP. This also achieves Godel's objective of defining intuitionistic propositional logic Int via classical proofs and provides a Brouwer-Heyting-Kolmogorov style provability semantics for Int (...) which resisted formalization since the early 1930s. LP may be regarded as a unified underlying structure for intuitionistic, modal logics, typed combinatory logic and λ-calculus. (shrink)

ABSTRACT In 1933 Gödel introduced an axiomatic system, currently known as S4, for a logic of an absolute provability, i.e. not depending on the formalism chosen ([God 33]). The problem of finding a fair provability model for S4 was left open. The famous formal provability predicate which first appeared in the Gödel Incompleteness Theorem does not do this job: the logic of formal provability is not compatible with S4. As was discovered in [Art 95], this defect of the formal provability (...) predicate can be bypassed by replacing hidden quantifiers over proofs by proof polynomials in a certain finite basis. The resulting Logic of Proofs enjoys a natural arithmetical semantics and provides an intended provability model for S4, thus answering a question left open by Gödel in 1933. Proof polynomials give an intended semantics for some other constructions based on the concept of provability, including intuitionistic logic with its Brouwer- Heyting- Kolmogorov interpretation, ?-calculus and modal ?-calculus. In the current paper we demonstrate how the intuitionistic propositional logic Int can be directly realized by proof polynomials. It is shown, that Int is complete with respect to this proof realizability. (shrink)

We use a method suggested by Kolmogorov complexity to examine some relations between Kolmogorov complexity and noncomputability. In particular we show that the method consistently gives us more information than conventional ways of demonstrating noncomputability . Also, many sets which are awkward to embed into the halting problem are easily shown noncomputable. We also prove a gap-theorem for outputting consecutive integers and find, for a given length n, a statement of length n with maximal proof length.

We investigate the initial segment complexity of random reals. Let K denote prefix-free Kolmogorov complexity. A natural measure of the relative randomness of two reals α and β is to compare complexity K and K. It is well-known that a real α is 1-random iff there is a constant c such that for all n, Kn−c. We ask the question, what else can be said about the initial segment complexity of random reals. Thus, we study the fine behaviour of (...) K for random α. Following work of Downey, Hirschfeldt and LaForte, we say that αK β iff there is a constant such that for all n, . We call the equivalence classes under this measure of relative randomness K-degrees. We give proofs that there is a random real α so that lim supn K−K=∞ where Ω is Chaitin's random real. One is based upon work of Solovay, and the other exploits a new idea. Further, based on this new idea, we prove there are uncountably many K-degrees of random reals by proving that μ=0. As a corollary to the proof we can prove there is no largest K-degree. Finally we prove that if n ≠ m then the initial segment complexities of the natural n- and m-random sets and Ω︀) are different. The techniques introduced in this paper have already found a number of other applications. (shrink)

We reconsider some classical natural semantics of integers in the perspective of Kolmogorov complexity. To each such semantics one can attach a simple representation of integers that we suitably effectivize in order to develop an associated Kolmogorov theory. Such effectivizations are particular instances of a general notion of “self-enumerated system” that we introduce in this paper. Our main result asserts that, with such effectivizations, Kolmogorov theory allows to quantitatively distinguish the underlying semantics. We characterize the families obtained (...) by such effectivizations and prove that the associated Kolmogorov complexities constitute a hierarchy which coincides with that of Kolmogorov complexities defined via jump oracles and/or infinite computations . This contrasts with the well-known fact that usual Kolmogorov complexity does not depend on the chosen arithmetic representation of integers, let it be in any base n ≥ 2 or in unary. Also, in a conceptual point of view, our result can be seen as a mean to measure the degree of abstraction of these diverse semantics. (shrink)

An infinite binary sequence X is Kolmogorov–Loveland random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence.One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as KL-randomness. Our (...) first main result states that KL-random sequences are close to Martin-Löf random sequences in so far as every KL-random sequence has arbitrarily dense subsequences that are Martin-Löf random. A key lemma in the proof of this result is that for every effective split of a KL-random sequence at least one of the halves is Martin-Löf random. However, this splitting property does not characterize KL-randomness; we construct a sequence that is not even computably random such that every effective split yields two subsequences that are 2-random. Furthermore, we show for any KL-random sequence A that is computable in the halting problem that, first, for any effective split of A both halves are Martin-Löf random and, second, for any computable, nondecreasing, and unbounded function g and almost all n, the prefix of A of length n has prefix-free Kolmogorov complexity at least n−g. Again, the latter property does not characterize KL-randomness, even when restricted to left-r.e. sequences; we construct a left-r.e. sequence that has this property but is not KL-stochastic and, in fact, is not even Mises–Wald–Church stochastic.Turning our attention to KL-stochasticity, we construct a non-empty class of KL-stochastic sequences that are not weakly 1-random; by the usual basis theorems we obtain such sequences that in addition are left-r.e., are low, or are of hyperimmune-free degree.Our second main result asserts that every KL-stochastic sequence has effective dimension 1, or equivalently, a sequence cannot be KL-stochastic if it has infinitely many prefixes that can be compressed by a factor of α<1. This improves on a result by Muchnik, who has shown that were they to exist, such compressible prefixes could not be found effectively. (shrink)

This paper continues the study of the metric topology on $2^{\mathbb {N}}$ that was introduced by S. Binns. This topology is induced by a directional metric where the distance from $Y\in2^{\mathbb {N}}$ to $X\in2^{\mathbb {N}}$ is given by \[\limsup_{n}\frac{C(X\upharpoonright n|Y\upharpoonright n)}{n}.\] This definition is closely related to the notions of effective Hausdorff and packing dimensions. Here we establish that this is a path-connected topology on $2^{\mathbb {N}}$ and that under it the functions $X\mapsto\operatorname{dim}_{\mathcal{H}}X$ and $X\mapsto\operatorname{dim}_{p}X$ are continuous. We also investigate (...) the scalar multiplication operation that was introduced by Binns. The multiplication of a real $X\in2^{\mathbb {N}}$ by an element $\alpha\in[0,1]$ represents a dilution of the information in $X$ by a factor of $\alpha$ . Our main result is to show that every regular real is the dilution of a real of Hausdorff dimension 1. That is, that the information in every regular real can be maximally compressed. (shrink)

A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x), f is a k(n)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the Kolmogorov function, (...) which assigns to each string x its Kolmogorov complexity: • For every underlying universal machine U, there is a constant a such that C is k(n)-enumerable only if k(n) ≥ n/a for almost all n. • For any given constant k, the Kolmogorov function is k-enumerable relative to an oracle A if and only if A is at least as hard as the halting problem. • There exists an r.e., Turing-incomplete set A such for every non-decreasing and unbounded recursive function k, the Kolmogorov function is k(n)-enumerable relative to A. The last result is obtained by using a relativizable construction for a nonrecursive set A relative to which the prefix-free Kolmogorov complexity differs only by a constant from the unrelativized prefix-free Kolmogorov complexity. Although every 2-enumerator for C is Turing hard for K, we show that reductions must depend on the specific choice of the 2-enumerator and there is no bound on the quantity of their queries. We show our negative results even for strong 2-enumerators as an oracle where the querying machine for any x gets directly an explicit list of all hypotheses of the enumerator for this input. The limitations are very general and we show them for any recursively bounded function g: • For every Turing reduction M and every non-recursive set B, there is a strong 2-enumerator f for g such that M does not Turing reduce B to f. • For every non-recursive set B, there is a strong 2-enumerator f for g such that B is not wtt-reducible to f. Furthermore, we deal with the resource-bounded case and give characterizations for the class ${\rm S}_{2}^{{\rm P}}$ introduced by Canetti and independently Russell and Sundaram and the classes PSPACE, EXP. • ${\rm S}_{2}^{{\rm P}}$ is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time tt-reduction which reduces A to every strong 2-enumerator for g. • PSPACE is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time Turing reduction which reduces A to every strong 2-enumerator for g. Interestingly, g can be taken to be the Kolmogorov function for the conditional space bounded Kolmogorov complexity. • EXP is the class of all sets A for which there is a polynomially bounded function g and a machine M which witnesses A ∈ PSPACEf for all strong 2-enumerators f for g. Finally, we show that any strong O(log n)-enumerator for the conditional space bounded Kolmogorov function must be PSPACE-hard if P = NP. (shrink)

This paper is devoted to the control problem of a nonlinear dynamical system obtained by a truncation of the two-dimensional Navier–Stokes equations with periodic boundary conditions and with a sinusoidal external force along the x-direction. This special case of the 2D N-S equations is known as the 2D Kolmogorov flow. Firstly, the dynamics of the 2D Kolmogorov flow which is represented by a nonlinear dynamical system of seven ordinary differential equations of a laminar steady state flow regime and (...) a periodic flow regime are analyzed; numerical simulations are given to illustrate the analysis. Secondly, an adaptive controller is designed for the system of seven ODEs representing the approximation of the dynamics of the 2D Kolmogorov flow to control its dynamics either to a steady-state regime or to a periodic regime; the value of the Reynolds number is determined using an update law. Then, a static sliding mode controller and a dynamic sliding mode controller are designed for the system of seven ODEs representing the approximation of the dynamics of the 2D Kolmogorov flow to control its dynamics either to a steady-state regime or to a periodic regime. Numerical simulations are presented to show the effectiveness of the proposed three control schemes. The simulation results clearly show that the proposed controllers work well. (shrink)

We study reals with infinitely many incompressible prefixes. Call $A \in 2^{\omega}$ Kolmogorot random if $(\exists^{\infty}n) C(A \upharpoonright n) \textgreater n - \mathcal{O}(1)$ , where C denotes plain Kolmogorov complexity. This property was suggested by Loveland and studied by $Martin-L\ddot{0}f$ , Schnorr and Solovay. We prove that 2-random reals are Kolmogorov random. Together with the converse-proved by Nies. Stephan and Terwijn [11]-this provides a natural characterization of 2-randomness in terms of plain complexity. We finish with a related characterization (...) of 2-randomness. (shrink)

t. 1. Filosofii︠a︡ ; Izbrannye predislovii︠a︡ ; I︠A︡zykoznanie -- t. 2. Filologii︠a︡ ; Vospominanii︠a︡ i nabli︠u︡denii︠a︡ ; Pami︠a︡ti uchiteleĭ i kolleg ; Prilozhenie : A.N. Kolmogorov, semioticheskie poslanii︠a︡.

We investigate the question of whether one can characterize complexity classes in terms of efficient reducibility to the set of Kolmogorov-random strings . This question arises because and , and no larger complexity classes are known to be reducible to in this way. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of universal machine in the definition of Kolmogorov complexity. What follows is a list of some of our main (...) results.• Although Kummer showed that, for every universal machine U there is a time bound t such that the halting problem is disjunctive truth-table reducible to in time t, there is no such time bound t that suffices for every universal machine U. We also show that, for some machines U, the disjunctive reduction can be computed in as little as doubly-exponential time.• Although for every universal machine U, there are very complex sets that are -reducible to , it is nonetheless true that . • Any decidable set that is polynomial-time monotone-truth-table reducible to is in .• Any decidable set that is polynomial-time truth-table reducible to via a reduction that asks at most f queries on inputs of size n lies in. (shrink)

Let K denote prefix-free Kolmogorov complexity, and let $K^A$ denote it relative to an oracle A. We show that for any n, $K^{\emptyset ^{(n)}}$ is definable purely in terms of the unrelativized notion K. It was already known that 2-randomness is definable in terms of K (and plain complexity C) as those reals which infinitely often have maximal complexity. We can use our characterization to show that n-randomness is definable purely in terms of K. To do this we extend (...) a certain “limsup” formula from the literature, and apply Symmetry of Information. This extension entails a novel use of semilow sets, and a more precise analysis of the complexity of $\Delta _2^0$ sets of minimal descriptions. (shrink)

What follows shall provide an introduction to a predominantly philosophical and polemical, but historically revealing, paper on the foundations of the theory of probability. The leading Russian probabilist Aleksandr Yakovlevich Khinchin wrote the paper in the late 1930s, commenting on a slightly older, but still competing approach to probability theory by Richard von Mises. Together with the even more influential Andrey Nikolayevich Kolmogorov, who was nine years his junior, Khinchin had revolutionized probability theory around 1930 by introducing the (...) modern measure-theoretic approach, which is still standard today and which allowed for a sufficiently general treatment of important new notions such as “stochastic processes.” This development had its first culmination in Kolmogorov's booklet, Grundbegriffe der Wahrscheinlichkeitsrechnung, written in German in 1933, which has exerted an enormous influence world wide. (shrink)

In Chapter I of his celebrated Foundations of Probability, A. N. Kolmogorov proposed an axiomatic treatment of the mathematical theory of probability—the approach that assimilated probability theory into measure theory. Kolmogorov followed his statement of the axioms with an account of how “we apply the theory of probability to the actual world of experiments.”.

This paper outlines a logical representation of certain aspects of the process of mathematical proving that are important from the point of view of Artificial Intelligence. Our starting point is the concept of proof-event or proving, introduced by Goguen, instead of the traditional concept of mathematical proof. The reason behind this choice is that in contrast to the traditional static concept of mathematical proof, proof-events are understood as processes, which enables their use in Artificial Intelligence in such contexts in which (...) problem-solving procedures and strategies are studied. We represent proof-events as problem-centred spatio-temporal processes by means of the language of the calculus of events, which adequately captures certain temporal aspects of proof-events (i.e. that they have history and form sequences of proof-events evolving in time). Further, we suggest a “loose” semantics for the proof events by means of Kolmogorov’s calculus of problems. Finally, we expose the intented interpretations for our logical model from the fields of automated theorem-proving and Web-based collective proving. (shrink)

The correspondence between Richard von Mises and George Pólya of 1919/20 contains reflections on two well-known articles by von Mises on the foundations of probability in the Mathematische Zeitschrift of 1919, and one paper from the Physikalische Zeitschrift of 1918. The topics touched on in the correspondence are: the proof of the central limit theorem of probability theory, von Mises' notion of randomness, and a statistical criterion for integer-valuedness of physical data. The investigation will hint at both the fruitfulness and (...) the limits of several of von Mises' notions such as ``collective'', ``distribution'' and ``complex adjuncts'' (characteristic functions) for further developments in probability theory and in ``directional statistics''. By pointing to the selectiveness of Pólya's criticism, the historical analysis shows the differing expectations of the two men with respect to the further development of the theory of probability and its applications. The paper thus gives a glimpse of the provisional state of the theory around 1920, before others such as P. Lévy (1886–1971) and A. N. Kolmogorov (1903–1987) stepped in and created a new paradigm for probability theory. (shrink)

We prove a completeness criterion for quasi-reducibility and generalize it to higher levels of the arithmetical hierarchy. As an application of the criterion we obtain Q-completeness of the set of all pairs such that the prefix-free Kolmogorov complexity of x is less than n.

Let ω be a Kolmogorov–Chaitin random sequence with ω1: n denoting the first n digits of ω. Let P be a recursive predicate defined on all finite binary strings such that the Lebesgue measure of the set {ω|∃nP(ω1: n )} is a computable real α. Roughly, P holds with computable probability for a random infinite sequence. Then there is an algorithm which on input indices for any such P and α finds an n such that P holds within the (...) first n digits of ω or not in ω at all. We apply the result to the halting probability Ω and show that various generalizations of the result fail. (shrink)

Cook and Reckhow [5] pointed out that $\mathcal {N}\mathcal {P} \neq co\mathcal {N}\mathcal {P}$ iff there is no propositional proof system that admits polynomial size proofs of all tautologies. The theory of proof complexity generators aims at constructing sets of tautologies hard for strong and possibly for all proof systems. We focus on a conjecture from [16] in foundations of the theory that there is a proof complexity generator hard for all proof systems. This can be equivalently formulated (for p-time (...) generators) without a reference to proof complexity notions as follows:•There exists a p-time function g stretching each input by one bit such that its range $rng(g)$ intersects all infinite $\mathcal {N}\mathcal {P}$ sets.We consider several facets of this conjecture, including its links to bounded arithmetic (witnessing and independence results), to time-bounded Kolmogorov complexity, to feasible disjunction property of propositional proof systems and to complexity of proof search. We argue that a specific gadget generator from [18] is a good candidate for g. We define a new hardness property of generators, the $\bigvee $ -hardness, and show that one specific gadget generator is the $\bigvee $ -hardest (w.r.t. any sufficiently strong proof system). We define the class of feasibly infinite $\mathcal {N}\mathcal {P}$ sets and show, assuming a hypothesis from circuit complexity, that the conjecture holds for all feasibly infinite $\mathcal {N}\mathcal {P}$ sets. (shrink)